The advent of miniaturization has led to ever denser electronic circuits. As the density of electronic circuits has increased, so too has the complexity and cost of testing. In an effort to reduce the cost and complexity of testing digital integrated circuits and, particularly, random logic digital circuits, various techniques such as partial-scan testing have been developed. Partial-scan testing, as described in U.S. Pat. No. 5,034,986, issued on Aug. 27, 1991, in the names of V. Agrawal et al., and assigned to the present assignee (incorporated by reference herein), is practiced by partitioning the circuit such that selected sequential elements (i.e., flip-flops) in the circuit are arranged as a shift register. Initially, the circuit is placed in a test mode and a known stream of test data is shifted into the shift register configured of the selected flip-flops, usually referred to as "scan" flip-flops. Thereafter, the integrated circuit is placed in its normal operating mode so as to react to the test data. Finally, the integrated circuit is returned to the test mode and the test data (as modified by the operation of the integrated circuit) is shifted out from the scan flip-flops for comparison to a reference data stream.
Partial scan testing may be improved, in the manner taught in my copending U.S. patent application, Ser. No. 813,521, "Partial Scan Built-In Self-Test Technique", filed Dec. 26, 1991, and assigned to the present assignee (incorporated by reference herein). As described in my co-pending application Ser. No. 813,521, such testing of an integrated circuit may be improved by the addition of built-in, self-test circuitry, including a test pattern generator and a compactor. Self-looping, non-scan flip-flops in the circuit are replaced with initializable flip-flops so that the integrated circuit can be set to an initial state prior to testing to obtain a deterministic signature.
While my partial-scan, built-in, self-test circuit achieves very high fault coverage (that is, the circuit can self-detect a high percentage of faults), there is a need to increase the level of fault coverage even higher. One traditional approach to increasing the level of fault coverage in built-in, self-test circuits has been to add "test points" at various nodes in the circuit. For purposes of discussion, a test point is defined as being either an observability point (i.e., a line coupled to a circuit node to facilitate observation of the signal at that node) or a control point, (i.e., either an AND or OR gate inserted between the node, and a line supplying the node with signals). Placement of test points in a built-in, self-test circuit presents little difficulty when the circuit is comprised purely of combinational elements (i.e, AND, OR, NAND, NOR, NOT and XOR gates). For such combinational circuits, test points can be selected using a known procedure for calculating a probabilistic measure of the controllability and observability of the nodes in the circuit. The controllability of a node is defined as the ability to excite a fault (e.g., a stuck-at-1 or a stuck-at-0 fault), whereas the observability of a node is defined as the ability to observe the effect of a fault at the node.
In contrast, placement of test points in a sequential circuit (i.e., a circuit containing one or more flip-flops) is a far more difficult problem, especially because the controllability-observability probabilistic calculations employed for test point determination in combinational circuits have traditionally been deemed inapplicable for sequential circuits. One current approach to adding test points in a sequential circuit is to perform fault simulation to determine optimal test point placement. Fault simulation is time consuming and quickly becomes impractical for even moderately large sequential circuits.
The non-scan portion of the partial-scan, built-in, self-test circuit described in my co-pending application Ser. No. 813,521 is a special type of sequential circuit, known as a near-acyclic circuit. A near-acyclic circuit is a synchronous sequential circuit (i.e., one which contains one or more flip-flops) having a corresponding directed graph which does not contain any cycle whose length is greater than one. Thus, in a near-acyclic circuit, there exist no flip-flop loops (a sequential chain of two or more flip-flops with the output of the last one in the chain being fed back to the input of the first flip-flop). An acyclic circuit may however contain one or more "self-looping" flip-flops, (i.e., a single flip-flop whose input is fed back to its output).
Thus, there is a need for a technique for enhancing the testability of a near-acyclic circuits by adding test points to such a circuit in an efficient manner.